package doublePtr

import "math"

/*
时间复杂度:O(n)
空间复杂度:O(1)

双指针
 */
func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	minVal, maxVal := math.MaxInt32, math.MinInt32
	start, end := 0, -1
	// 分段来看，其实整个切片被分成三段，第一段和第三段都是有序的（从小到大排列），第二段是乱序的，而我们求的就是第二段的长度
	// 假设第一段最右边的值为x, 第三段最左边的值为y，第二段中最大值和最小值分别为zMax和zMin
	// 则有zMin >= x, zMax<=y，因为如果zMin<x, 则表示zMin本来应该是在第一段的，那么表示第一段也应该是乱序的，这与我们假设的前提不符
	// 同时我们可以推测出：zMin一定不在第二段的左边界，zMax也一定不在第二段的右边界，因为如果zMin在第二段左边界，
	//	则第一段应该包括zMin(由于zMin>=x,所以第一段包含zMin后仍是有序的，不与前提矛盾)
	// 所以得出结论：zMin一定不在第二段左边界，zMax一定不在第二段右边界
	//
	// 通过上面的结论，我们又可得出：第二段左边界值一定大于zMin, 第二段右边界值一定小于zMax
	// 我们要找的是第二段的长度，可以通过找到第二段的左右边界start和end, 然后计算 end - start +1 得到
	// 要找到end，则我们从左到右遍历，遇到更大的值更新maxVal, 最终遍历到第二段时，我们会取到zMax的值为maxVal
	// 然后,每次遍历到的值只要小于maxVal, 我们就将end的值更新为当前索引i, 也就是说当我们取到zMax作为maxVal之后继续在第二段遍历,
	// 只要还在第二段,则遍历到的值一定都比zMax要小,直到我们遍历到第二段的右边界,更新end为右边界值之后, 进入第三段,而zMax <=y, 所以每次遇到的
	// 值都将比上一次的maxVal要大,不会再遇到比maxVal更小的值,也就不会再更新end了
	for i := 0; i < n; i++ {
		if maxVal <= nums[i] {
			maxVal = nums[i]
		} else {
			end = i
		}

		if minVal >= nums[n-1-i] {
			minVal = nums[n-1-i]
		} else {
			start = n - 1 - i
		}
	}
	return end - start + 1
}
